Considering the low robustness of existing watermarking algorithms based on High Efficiency Video Coding (HEVC) standard, a robust video watermarking algorithm for HEVC based on intra-frame prediction modes of multi-partitioning was proposed. Firstly, in order to eliminate the intra-frame error propagation after embedding the watermark, embeddable regions were selected and the texture direction was calculated for 4×4 luminance blocks. Secondly, a scheme was proposed that the 33 angular prediction modes were divided into four pattern sets, which were recorded as follows:upper horizontal, lower horizontal, upper vertical, lower vertical. Finally, the four pattern sets were mapped to the values of the current and next to be embedded watermarks. Once the current 4×4 luminance blocks met the pattern sets, the current 33 angular prediction modes were truncated into the current pattern sets and the watermark was embedded. The watermark was extracted by the texture direction and four prediction pattern sets at decoding side. The experimental results show that, the average Peak Signal to Noise Ratio (PSNR) of the proposed algorithm is almost unchanged. In addition, the proposed algorithm achieves the Bit Error Rate (BER) of 14.1% under re-encoded attacks. Therefore, the proposed algorithm has low video distortion and can well resist the re-encoded attacks in robustness.